package cn.kent.simple;


/**
 * 108. 将有序数组转换为二叉搜索树
 * 1.中序遍历，总是选择中间位置左边的数字作为根节点
 * 2.中序遍历，总是选择中间位置右边的数字作为根节点
 * 3.中序遍历，总是选择中间位置数字作为根节点
 */
public class SortedArrayToBST {

    public static void main(String[] args) {
        int[] nums = {};
        sortedArrayToBST(nums);
    }

    // 1.中序遍历，总是选择中间位置左边的数字作为根节点
    public static TreeNode sortedArrayToBST(int[] nums) {
        return setRootNode(0, nums.length - 1, nums);
    }

    private static TreeNode setRootNode(int l, int r, int[] nums) {
        if (l > r) {
            return null;
        }
        int mid = (r + l) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = setRootNode(l, mid - 1, nums);
        root.right = setRootNode(mid + 1, r, nums);
        return root;
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
